package leetcode.N1_N100;

import leetcode.comm.ListNode;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/14 8:57 下午
 */
public class N86 {

    public static void main(String[] args) {
        System.out.println(partition(ListNode.generate(1, 4, 3, 2, 5, 2), 3));
    }

    public static ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode smallHead = new ListNode(0);
        ListNode smallLast = smallHead;
        ListNode largeHead = new ListNode(0);
        ListNode largeLast = largeHead;
        ListNode next = head;
        while (next != null) {
            if (next.val < x) {
                smallLast = smallLast.next = next;
            } else {
                largeLast = largeLast.next = next;
            }
            next = next.next;
            largeLast.next = smallLast.next = null;
        }
        smallLast.next = largeHead.next;
        return smallHead.next;
    }

}
